package arithmetic;

import java.util.Arrays;

/**
 * @author jiangfeng 2019/8/4 17:59
 * 八皇后问题
 *
 * https://blog.csdn.net/Hackbuteer1/article/details/6657109
 */
public class EightQueen {

    static int count =0;


    public static void main(String[] args) {
        queen(8);
    }

    /**
     * n皇后问题的递归解法.
     * todo 回溯算法求解
     * @param n
     */
    public static void queen(int n) {
        int[] arr = new int[n * n];
        queen_(0, arr, n);
        System.out.println("有解数:" + count);
    }

    /**
     * 八皇后问题递归求解器
     * @param row 当前递归的行数
     * @param arr 八皇后棋盘数组 n*n一维,根据下标自己逻辑解析为n*n二维
     * @param n 棋盘的大小
     */
    private static void queen_(int row, int[] arr, int n) {
        if (row == n) {
            printResult(arr);
            System.out.println();
            count++;
        } else {
            for (int i = 0; i < n; i++) { //试探row行的 每一列是否可放
                if (canPlace(arr, i + row*n, n)) {
                    arr[i + row*n] = 1;
                    queen_(row + 1, arr, n);//递归到下一行去
                    arr[i + row*n] = 0; // 说明此处不能放子
                }
            }
        }
    }


    /**
     * 检测是否横竖斜均无棋子
     * @param arr
     * @param i 第i个棋子是否可放
     * @return
     */
    private static boolean canPlace(int[] arr, int i, int n) {
        // 第i个棋子的  左上,正上,右上不能有棋子
        int row = i / n;
        int col = i % n;
        for (int j = 0; j < row; j++) { // 第row行不用考虑
            if (arr[j * n + col] > 0) { // 正上不能有子
                return false;
            }
            if (col - row + j >= 0 && arr[j * n + col - row + j] > 0) { // 左斜上方不能有子
                return false;
            }
            if (col + row - j < n && arr[j * n + col + row - j] > 0) { // 右斜上方不能有子
                return false;
            }
        }
        for (int j = 0; j < col; j++) {
            if (arr[row * n + j] > 0) { // 第row行不能落子
                return false;
            }
        }
        return true;
    }


    /**
     * 用一维数组表示结果:0代表未放子,1表示放子
     * 打印结果
     * @param arr
     */
    private static void printResult(int[] arr){
        int n = ((Double) Math.sqrt(arr.length)).intValue();// 开平方
        for (int i = 0; i < arr.length; i++) {
            if ((i + 1) % n == 0) {
                System.out.println(arr[i]);
            } else {
                System.out.print(arr[i] + " ");
            }
        }
    }


}
